package 中等.数学;

import java.util.HashSet;
import java.util.Set;

/**
 * 给你一个正整数数组 nums ，对 nums 所有元素求积之后，找出并返回乘积中 不同质因数 的数目。
 * 注意：
 * 质数 是指大于 1 且仅能被 1 及自身整除的数字。
 * 如果 val2 / val1 是一个整数，则整数 val1 是另一个整数 val2 的一个因数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/distinct-prime-factors-of-product-of-array
 */
public class 数组乘积中的不同质因数数目_6279 {

    public static void main(String[] args) {

        System.out.println(distinctPrimeFactors(new int[]{2, 4, 8, 16}));

    }

    /**
     * 计算每个数的质因数+哈希表去重
     */
    public static int distinctPrimeFactors(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            int i = 2;
            while (i * i <= num) {
                while (num % i == 0) {
                    set.add(i);
                    num /= i;
                }
                i++;
            }
            if (num > 1) set.add(num);
        }

        return set.size();
    }

}
